import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yang
 * Date: 2022-07-18
 * Time: 15:50
 */

public class HeapSort {
    private static void swap(int a,int b,int[] array){
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
    public static void selectSort(int[] array){
        for (int i = 0 ; i < array.length; i++) {
            int min_index = i;
            for (int j = i; j < array.length; j++) {
                if(array[min_index] > array[j]){
                    min_index = j;
                }
            }
            swap(min_index,i,array);
        }
    }

    private static void shiftDown(int parent,int[] elem,int limit){
        int child = 2*parent + 1;
        while(child < limit){
            if(child+1 < limit && elem[child] < elem[child + 1]){
                child++;
            }
            if(elem[parent] < elem[child]){
                swap(parent,child,elem);
                parent = child;
                child = 2*parent + 1;
            }
            else break;
        }
    }

    public static void heapSort(int[] array){
        for(int parent = (array.length-1-1)/2; parent >= 0; parent--){
            shiftDown(parent,array,array.length);
        }
        for (int i = array.length-1; i >= 0; i--) {
            swap(0,i,array);
            shiftDown(0,array,i);
        }
    }

    public static void main(String[] args) {
        int[] arr = {4,3,7,2,8,1,12,6,12,5,9};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
